﻿\subsection{Результаты экспериментов}
\label{subsection:bigexp-results}

В таблице~\ref{table:bigexp-rates} приведены оценки индексов роста 
некоторых языков первого уровня. Для языков над алфавитом не более чем из 8
букв наш алгоритм позволял построить любое конечное приближение, антисловарь и распознающий
автомат которого помещаются в 2 Гб оперативной памяти ПК. Поскольку мы используем
кодировку Пансьё, объём используемой памяти зависит только от размера построенного антисловаря,
но не от размера алфавита, что позволяет нам вычислять оценки индексов роста языков
первого уровня над большими алфавитами.

Численные эксперименты показали, что значения индексов роста
$(k/(k{-}1)^{+}$-свободного
и $(k{-}1)/(k{-}2)$-свободного языков над алфавитом размера $k$ достаточно близки,
хотя уже при переходе от запрещённой экспоненты $(k{-}1)/(k{-}2)$ к $(k{-}1)/(k{-}2)^{+}$
индекс роста возрастает более чем на единицу (\cite{Shur-Algo}).
Мы предполагаем, что все приведённые в таблице
оценки отличаются от реальных значений индексов роста не более чем на $0.0005$.
При этом чем больше размер алфавита, тем точнее полученная оценка.

\newpage
\input bigexp/tables/all.tex

Также отметим, что в приведённом алгоритме рекурсивного перебора корней можно
эффективно использовать параллельные вычисления. Каждый поток будет рекурсивно
перебирать все корни с заданным префиксом и возвращать список построенных
минимальных запрещённых слов. Объединение этих списков будет давать полное
приближение антисловаря языка. Такой подход позволяет получить ещё более
точные оценки рассматриваемых языков.

